#include"sq_list.h"
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

Status sqlist_init(sq_list *sl, size_t struct_size)
{
	sl->data = malloc(SQ_INIT_SIZE * struct_size);
	if(!sl->data)
		exit(OVERFLOW);
	
	sl->size = SQ_INIT_SIZE;
	sl->length = 0;
	return SUCCESS;
}

void *sqlist_getelem(const sq_list *sl, size_t i, size_t struct_size)
{
	void *p = sl->data;
	p += (i - 1) * struct_size;
	return p;
}

/* struct_cmp returns 0 if two elems is equal */
/* return 0 if not find */
size_t sqlist_locateelem(const sq_list *sl,const void *e, 
		int struct_cmp(const void *,const void *), 
		size_t struct_size)
{
	size_t i = 1;
	void *p = sl->data;
	while(i <= sl->length){
		if(struct_cmp(p,e) == 0)
			return i;
		i++;
		p += struct_size;
	}
	return 0;
}

Status sqlist_insert(sq_list *sl, size_t i, const void *e,
		     size_t struct_size)
{
	void *p,*q;

	if(i < 1 || i > sl->length + 1)
		return ERROR;
	
	if(sl->length >= sl->size){
		p = realloc(sl->data, (sl->size + SQ_INCREMENT)	* struct_size);
		if(!p) exit(OVERFLOW);
		sl->data = p;
		sl->size += SQ_INCREMENT;
	}
	p = sl->data + (sl->length - 1) * struct_size;
	q = sl->data + (i - 1) * struct_size;
	while(p >= q){
		memcpy(p + struct_size, p, struct_size);
		p -= struct_size;
	}
	memcpy(q, e, struct_size);
	++sl->length;
	return SUCCESS;
}

Status sqlist_delete(sq_list *sl, size_t i, void *e, size_t struct_size)
{
	void *p, *q;
	
	if(i < 1 || i > sl->length)
		return ERROR;
	
	p = sl->data + (i - 1) * struct_size;
	memcpy(e, p, struct_size);
	
	q = sl->data + (sl->length -1) * struct_size;
	while(p < q ){
		memcpy(p, p + struct_size, struct_size);
		p += struct_size;
	}
	
	--sl->length;
	return SUCCESS;
}


void sqlist_traverse(const sq_list *sl, Bool visit(const void *),size_t struct_size)
{
	int i;
	for(i = 0; i < sl->length; i++)
		if(!visit(sl->data + i * struct_size))
			exit(ERROR);
	
}

void sqlist_merge(const sq_list* s1,const sq_list* s2, sq_list *s3,
			int compare(const void *,const void *), size_t struct_size)
{
	void *p1,*p2,*p1_last,*p2_last;
	p1 = s1->data;
	p2 = s2->data;
	p1_last = p1 + s1->length * struct_size;
	p2_last = p2 + s2->length * struct_size;
	p2 = s2->data;
	sqlist_init(s3,struct_size);
	while(p1 < p1_last && p2 < p2_last){
		if(compare(p1, p2) < 0){
			sqlist_insert(s3, s3->length + 1, p1, struct_size);
			p1 += struct_size;
		}else{
			sqlist_insert(s3, s3->length + 1, p2, struct_size);
			p2 += struct_size;
		}
	}
	while(p1 < p1_last){
		sqlist_insert(s3, s3->length + 1, p1, struct_size);
		p1 += struct_size;
	}
	while(p2 < p2_last){
		sqlist_insert(s3, s3->length + 1, p2, struct_size);
		p2 += struct_size;
	}
}
